// https://leetcode.cn/problems/different-ways-to-add-parentheses/
// Created by ade on 2022/9/9.
// 输入：expression = "2*3-4*5"
//输出：[-34,-14,-10,-10,10]
//解释：
//(2*(3-(4*5))) = -34
//((2*3)-(4*5)) = -14
//((2*(3-4))*5) = -10
//(2*((3-4)*5)) = -10
//(((2*3)-4)*5) = 10
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>

using namespace std;

class Solution {
public:
    unordered_map <string, vector<int>> res = {};

    vector<int> diffWaysToCompute(string s) {
        if (res.find(s) != res.end()) return res[s];
        if (s.find_first_of("+-*") == s.npos) return {stoi(s)};
        vector<int> ans = {};
        int pos = 0;
        while ((pos = s.find_first_of("+-*", pos + 1)) != s.npos) {
            vector<int> left = diffWaysToCompute(s.substr(0, pos)), right = diffWaysToCompute(s.substr(pos + 1));
            for (auto l : left)
                for (auto r : right)
                    ans.push_back(s[pos] == '+' ? l + r : s[pos] == '-' ? l - r : l * r);

        }
        res[s] = ans;
        return res[s];
    }
};

int main() {
    Solution so;
    string expression = "2*3-4*5";
    auto res = so.diffWaysToCompute(expression);
    for (auto i:res) {
        cout << i << ",";
    }
    cout << endl;
    return 0;
}